package com.autumn.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * n阶楼梯，每次爬1个或2个台阶，爬到顶共有多少种不同的方法，n为正整数
 */
public class Algorithm01ClimbStairs {
    /**
     * 解法一：递归
     *
     * @param n
     * @return
     */
    public static int climbStairsByRecursive(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairsByRecursive(n - 1) + climbStairsByRecursive(n - 2);
    }

    private static Map<Integer, Integer> storeMap = new HashMap<>();
    /**
     * 解法二：递归 + HashMap存储中间计算结果
     *
     * @param n
     * @return
     */
    public static int climbStairsByRecursiveAndMap(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (null != storeMap.get(n)){
            return storeMap.get(n);
        } else {
          int result = climbStairsByRecursiveAndMap(n-1) + climbStairsByRecursiveAndMap(n-2);
          storeMap.put(n, result);
          return result;
        }
    }

    /**
     * 解法三：for循环：自底向上累加
     * @param n
     * @return
     */
    public static int climbStairsByFor(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int result = 0;
        int pre = 2;
        int prePre = 1;
        for (int i = 3; i <= n; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }

    public static void main(String[] args) {
        long start1 = System.currentTimeMillis();
        int count1 = climbStairsByRecursive(100);
        long end1 = System.currentTimeMillis();
        System.out.println("100层爬楼梯共" + count1 + "种方法，递归耗时：" + (end1 - start1));
        // 测试结果：100层已耗时巨久，等不下去

        long start2 = System.currentTimeMillis();
        int count2 = climbStairsByRecursiveAndMap(100);
        long end2 = System.currentTimeMillis();
        System.out.println("100层爬楼梯共" + count2 + "种方法，递归加Map耗时：" + (end2 - start2));
        // 测试结果：性能有所提升，但层数若太多就栈溢出了

        long start3 = System.currentTimeMillis();
        int count3 = climbStairsByFor(100);
        long end3 = System.currentTimeMillis();
        System.out.println("100层爬楼梯共" + count3 + "种方法，for循环耗时：" + (end3 - start3));
        // 测试结果：性能最佳，递归加Map会栈溢出的层数仍旧耗时极短
    }

}
